package chapter03;
import chapter02.MyUtil;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class input01 {
    static int n;
    public static void main(String[] args){
       // inputfile();
        int[][] r=new int[n][n];
        //boat();

    }
    public static void path(int i,int j,int[][] s) {
        if(s[i][j]==0) {
            if(i==0){
                System.out.println("最优的路径为：");
                System.out.print(0);
            }
            System.out.print("-->"+j);
            return;
        }
        path(i, s[i][j], s);
        path(s[i][j], j, s);
    }
    public static  void inputfile()  {
        FileInputStream fileInputStream = null;
        try {
            fileInputStream = new FileInputStream("C:\\Users\\levovo\\Desktop\\算法实验2\\boat1.txt");
        } catch (FileNotFoundException e) {

            e.printStackTrace();
        }
        Scanner scanner =new Scanner(fileInputStream);
        int n=scanner.nextInt();
        int[][] r=new int[n][n];
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j <n; j++) {
                r[i][j]=scanner.nextInt();
            }

        }

        MyUtil.printM(r, 0, 5);
        //System.out.println(n);
//        int m[][]=scanner.nextInt();

    }
    public static  void boat_2(int[][] r, int[][] s){

        for(int d=3;d <= n;d++){//区间的站点数
            for (int i = 0; i <=n-d; i++) {//起点i，终点
                int j=i+d-1;
                for (int k = i+1; k <j ; k++) {//枚举决策点k
                    if(r[i][j]>r[i][k]+r[k][j]){
                        r[i][j]=r[i][k]+r[k][j];
                        s[i][j]=k;
                    }
                }

            }
        }
    }
    public static  void boat() {
        FileInputStream fileInputStream = null;
        try {
            fileInputStream = new FileInputStream("C:\\Users\\levovo\\Desktop\\算法实验2\\boat1.txt");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        Scanner scanner =new Scanner(fileInputStream);
        int n=scanner.nextInt();
       // System.out.println(n);
        int[][] r=new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                r[i][j]=scanner.nextInt();

                //System.out.println(j);

            }
        }
        System.out.println("站点租金矩阵表示");
        MyUtil.printM(r,  0, 4);
        int[][] s=new int[n][n];
        for(int d=3;d<=n;d++){//区间的站点数
            for (int i = 0; i <=n-d; i++) {//起点i，终点
                int j=i+d-1;
                for (int k = i+1; k <j ; k++) {//枚举决策点k
                    if(r[i][j]>r[i][k]+r[k][j]){
                        r[i][j]=r[i][k]+r[k][j];
                        s[i][j]=k;
                    }
                }

            }
        }//
        System.out.println("最少的租金为：");
        System.out.println(r[0][n-1]);
        path(0,n-1,s);
    }
}
